{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Removing Minimum Number of Magic Beans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #prefix-sum #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #前缀和 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumRemoval"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #拿出最少数目的魔法豆"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个 <strong>正整数&nbsp;</strong>数组&nbsp;<code>beans</code>&nbsp;，其中每个整数表示一个袋子里装的魔法豆的数目。</p>\n",
    "\n",
    "<p>请你从每个袋子中&nbsp;<strong>拿出</strong>&nbsp;一些豆子（也可以<strong>&nbsp;不拿出</strong>），使得剩下的 <strong>非空</strong> 袋子中（即 <strong>至少还有一颗</strong>&nbsp;魔法豆的袋子）魔法豆的数目&nbsp;<strong>相等</strong>。一旦把魔法豆从袋子中取出，你不能再将它放到任何袋子中。</p>\n",
    "\n",
    "<p>请返回你需要拿出魔法豆的 <strong>最少数目</strong>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>beans = [4,1,6,5]\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>\n",
    "- 我们从有 1 个魔法豆的袋子中拿出 1 颗魔法豆。\n",
    "  剩下袋子中魔法豆的数目为：[4,<u><strong>0</strong></u>,6,5]\n",
    "- 然后我们从有 6 个魔法豆的袋子中拿出 2 个魔法豆。\n",
    "  剩下袋子中魔法豆的数目为：[4,0,<u><strong>4</strong></u>,5]\n",
    "- 然后我们从有 5 个魔法豆的袋子中拿出 1 个魔法豆。\n",
    "  剩下袋子中魔法豆的数目为：[4,0,4,<u><strong>4</strong></u>]\n",
    "总共拿出了 1 + 2 + 1 = 4 个魔法豆，剩下非空袋子中魔法豆的数目相等。\n",
    "没有比取出 4 个魔法豆更少的方案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>beans = [2,10,3,2]\n",
    "<b>输出：</b>7\n",
    "<strong>解释：</strong>\n",
    "- 我们从有 2 个魔法豆的其中一个袋子中拿出 2 个魔法豆。\n",
    "  剩下袋子中魔法豆的数目为：[<u><strong>0</strong></u>,10,3,2]\n",
    "- 然后我们从另一个有 2 个魔法豆的袋子中拿出 2 个魔法豆。\n",
    "  剩下袋子中魔法豆的数目为：[0,10,3,<u><strong>0</strong></u>]\n",
    "- 然后我们从有 3 个魔法豆的袋子中拿出 3 个魔法豆。\n",
    "  剩下袋子中魔法豆的数目为：[0,10,<u><strong>0</strong></u>,0]\n",
    "总共拿出了 2 + 2 + 3 = 7 个魔法豆，剩下非空袋子中魔法豆的数目相等。\n",
    "没有比取出 7 个魔法豆更少的方案。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= beans.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= beans[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [removing-minimum-number-of-magic-beans](https://leetcode.cn/problems/removing-minimum-number-of-magic-beans/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [removing-minimum-number-of-magic-beans](https://leetcode.cn/problems/removing-minimum-number-of-magic-beans/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,1,6,5]', '[2,10,3,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        beans.sort()\n",
    "        l = len(beans)\n",
    "        b = beans[0] - 1\n",
    "        sleft = 0\n",
    "        sright = sum(beans)\n",
    "        ans = sright\n",
    "        for i in range(l):\n",
    "            take = sleft + sright - beans[i] * (l - i)\n",
    "            if ans > take:\n",
    "                ans = take\n",
    "            sleft += beans[i]\n",
    "            sright -= beans[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        s = sum(beans)\n",
    "        n = len(beans)\n",
    "\n",
    "        beans = sorted(beans)\n",
    "\n",
    "        # print(s,n)\n",
    "\n",
    "        res = s\n",
    "\n",
    "        for i in range(n):\n",
    "            tmp = s-beans[i]*(n-i)\n",
    "            if res>tmp:\n",
    "                res=tmp\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        beans.sort()\n",
    "        l = len(beans)\n",
    "        b = beans[0] - 1\n",
    "        sleft = 0\n",
    "        sright = sum(beans)\n",
    "        ans = sright\n",
    "        for i in range(l):\n",
    "            take = sleft + sright - beans[i] * (l - i)\n",
    "            if ans > take:\n",
    "                ans = take\n",
    "            sleft += beans[i]\n",
    "            sright -= beans[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        minbeans=-1\n",
    "        sum1=sum(beans)\n",
    "        beans_1=sorted(beans)\n",
    "        bea=-1\n",
    "        for i in range(len(beans_1)):\n",
    "            if bea==beans_1[i]:\n",
    "                continue\n",
    "            if beans_1[i]*(len(beans)-i)>minbeans:\n",
    "                minbeans=beans_1[i]*(len(beans)-i)\n",
    "            bea=beans_1[i]\n",
    "        return sum1-minbeans\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        beans.sort()\n",
    "        s = sum(beans)\n",
    "        n = len(beans)\n",
    "        x = 0\n",
    "        ans = 1e10\n",
    "        for i,bean in enumerate(beans):\n",
    "            ans = min(ans,s-(n-i)*bean+x)\n",
    "            s -= bean\n",
    "            x += bean\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        n = len(beans)\n",
    "        beans.sort()\n",
    "        tot = sum(beans)\n",
    "        ans = tot\n",
    "        for i in range(n):\n",
    "            ans = min(ans, tot - (n - i) * beans[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        beans.sort()\n",
    "        n = len(beans)\n",
    "        cnt = totalSum = sum(beans)\n",
    "        prev = 0\n",
    "        for i in range(n):\n",
    "            cnt = min(cnt, prev + totalSum - beans[i] * (n - i))\n",
    "            prev += beans[i]\n",
    "            totalSum -= beans[i]\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        beans.sort()\n",
    "        entire = sum(beans)\n",
    "        res = entire\n",
    "        remain = 0\n",
    "        for i in range(len(beans)):\n",
    "            remain = beans[i] * (len(beans)-i)\n",
    "            if entire - remain <res :\n",
    "                res = entire - remain        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        # 题意取豆\n",
    "        return sum(beans)-max((len(beans)-i)*v for i, v in enumerate(sorted(beans)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        n, total = len(beans), sum(beans)\n",
    "        beans.sort()\n",
    "        ans = inf\n",
    "        for i, num in enumerate(beans):\n",
    "            ans = min(ans, total - num * (n-i))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        n = len(beans)\n",
    "        beans.sort()\n",
    "        total = sum(beans)\n",
    "        res = total \n",
    "        for i in range(n):\n",
    "            res = min(res, total - beans[i] * (n-i))\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: list) -> int:\n",
    "        beans.sort()\n",
    "        # print(beans)\n",
    "        length, total = len(beans), sum(beans)\n",
    "        ans, last = 10**10, 0\n",
    "        for idx, c in enumerate(beans):\n",
    "            if c == last:\n",
    "                continue\n",
    "            last = c\n",
    "            cur = total - (length - idx) * c\n",
    "            # print(idx, c, cur)\n",
    "            ans = min(ans, cur)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        beans.sort()\n",
    "        s = sum(beans)\n",
    "        n = len(beans)\n",
    "        ans = 1e10\n",
    "        for i,bean in enumerate(beans):\n",
    "            ans = min(ans,s-(n-i)*bean)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        # 从寻找最少数目的魔法都转化为求剩余豆豆最多，而且这个那豆豆和发发抖社讯手续谷关\n",
    "        # 排序\n",
    "        # 枚举最终非空带的剩余豆豆数，枚举所有点不如枚举beans中的值，因为总能找到一个更大的值，使得剩余豆豆可以变的更多，所以枚举每个bean,小于bean全部扔掉，大于bean减少到bean\n",
    "        # 对于每个高度来说，最终剩余的魔法都等于（n-i）*bean,找到最大值等于剩余最多，然后total-max==拿出最少\n",
    "        beans.sort()\n",
    "        remain=0\n",
    "        n=len(beans)\n",
    "        for i,x in enumerate(beans):\n",
    "            remain=max(remain,(n-i)*x)\n",
    "        return sum(beans)-remain\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        n = len(beans)\n",
    "        beans.sort()\n",
    "        total = sum(beans)   # 豆子总数\n",
    "        res = total   # 最少需要移除的豆子数\n",
    "        for i in range(n):\n",
    "            res = min(res, total - beans[i] * (n - i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        beans.sort()\n",
    "        ans = sum(beans)\n",
    "        l = 0\n",
    "        r = ans\n",
    "        n = len(beans)\n",
    "        for i in range(n):\n",
    "            r -= beans[i]\n",
    "            ans = min(ans, l + r - beans[i] * (n-i-1) )\n",
    "            l += beans[i]\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        beans.sort()\n",
    "        allSum = sum(beans)\n",
    "        ans = inf\n",
    "        n = len(beans)\n",
    "        for i in range(n):\n",
    "            ans = min(allSum - (n - i) * beans[i], ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        n = len(beans)\n",
    "        s = sum(beans)\n",
    "        ans = s\n",
    "        for i,b in enumerate(sorted(beans)):\n",
    "            ans = min(ans,s-(n-i)*b)\n",
    "        return ans            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        beans.sort()\n",
    "        n = len(beans)\n",
    "        cnt = totalSum = sum(beans)\n",
    "        prev = 0\n",
    "        for i in range(n):\n",
    "            cnt = min(cnt, prev + totalSum - beans[i] * (n - i))\n",
    "            prev += beans[i]\n",
    "            totalSum -= beans[i]\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        beans.sort()\n",
    "        n = len(beans)\n",
    "        cnt = totalSum = sum(beans)\n",
    "        prev = 0\n",
    "        for i in range(n):\n",
    "            cnt = min(cnt, prev + totalSum - beans[i] * (n - i))\n",
    "            prev += beans[i]\n",
    "            totalSum -= beans[i]\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        beans = sorted(beans)\n",
    "        all_beans = sum(beans)\n",
    "        # diff = [beans[0]] + [beans[i]-beans[i-1] for i in range(1, len(beans))]\n",
    "        # print(diff)\n",
    "        # post_diff_sum = list(accumulate(reversed(diff)))\n",
    "        # print(post_diff_sum)\n",
    "        # pre_sum = [0] + list(accumulate(beans))\n",
    "        # print(pre_sum)\n",
    "        min_take = inf\n",
    "        beans_count = len(beans)\n",
    "        for i in range(beans_count):\n",
    "            temp = all_beans - beans[i] * (beans_count - i)\n",
    "            min_take = min(min_take, temp)\n",
    "        return min_take\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        return sum(beans) - max((len(beans) - i) * v for i, v in enumerate(sorted(beans)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        n,res,t,sorted_beans = len(beans),sum(beans),sum(beans),sorted(beans)\n",
    "        return min(t-(n-i)*sorted_beans[i] for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        '''\n",
    "        方法1： 暴力： 假设最终都是x，那么对于x，统计需要拿的豆子。 如果>x,拿i-x 否则<x，拿i全部   超时~\n",
    "        方法2： tip1：每次x一定是选取到bean中的某个值，tip2：总豆子是是不变的=留下的+拿走的，给bean排序，假设留下的是bean[i],那么留下的总和就是 (len-i)*bean[i]\n",
    "        '''\n",
    "        # 方法1：超时 (n2)\n",
    "        # maxx = max(beans)\n",
    "        # ans = sum(beans)+1\n",
    "        # for i in range(1,maxx+1,1):\n",
    "        #     summ = 0\n",
    "        #     for v in beans:\n",
    "        #         if v<i:\n",
    "        #             summ += v\n",
    "        #         else:\n",
    "        #             summ += v-i\n",
    "        #     ans = min(ans,summ)\n",
    "        # return ans\n",
    "\n",
    "        #方法2\n",
    "        beans.sort()\n",
    "        summ = sum(beans)\n",
    "        ans = summ\n",
    "        n = len(beans)\n",
    "        for i,v in enumerate(beans):\n",
    "            ans = min(ans, summ-v*(n-i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        n,res,t,sorted_beans = len(beans),sum(beans),sum(beans),sorted(beans)\n",
    "        return min(t-(n-i)*sorted_beans[i] for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        beans.sort()\n",
    "        l = len(beans)\n",
    "        b = beans[0] - 1\n",
    "        sleft = 0\n",
    "        sright = sum(beans)\n",
    "        ans = sright\n",
    "        for i in range(l):\n",
    "            if beans[i] > b:\n",
    "                b = beans[i]\n",
    "                take = sleft + sright - b * (l - i)\n",
    "                if ans > take:\n",
    "                    ans = take\n",
    "            sleft += beans[i]\n",
    "            sright -= beans[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        beans.sort()\n",
    "        current_sum = sum(beans)\n",
    "        res = float('inf')\n",
    "        length = len(beans)\n",
    "        for i in range(len(beans)):\n",
    "            # let this point to be the same line\n",
    "            temp_sum = (length - i) * beans[i]\n",
    "            res = min(res, current_sum - temp_sum)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        return sum(beans) - max((len(beans) - i) * v for i, v in enumerate(sorted(beans)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        beans.sort()\n",
    "        l = len(beans)\n",
    "        b = beans[0] - 1\n",
    "        sleft = 0\n",
    "        sright = sum(beans)\n",
    "        ans = sright\n",
    "        for i in range(l):\n",
    "            if beans[i] > b:\n",
    "                b = beans[i]\n",
    "                take = sleft + sright - b * (l - i)\n",
    "                if ans > take:\n",
    "                    ans = take\n",
    "            sleft += beans[i]\n",
    "            sright -= beans[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        beans.sort()\n",
    "        S = sum(beans)\n",
    "        res = inf\n",
    "        temp = 0\n",
    "        n = len(beans)\n",
    "        for idx,i in enumerate(beans):\n",
    "            res = min(res,(S-temp)-(n-idx)*i + temp)\n",
    "            temp += i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        n = len(beans)\n",
    "        beans.sort()\n",
    "        total = sum(beans)   # 豆子总数\n",
    "        res = total   # 最少需要移除的豆子数\n",
    "        for i in range(n):\n",
    "            res = min(res, total - beans[i] * (n - i))\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        if len(beans) == 1:\n",
    "            return 0\n",
    "        beans.sort()\n",
    "\n",
    "        sum_ = sum(beans)\n",
    "\n",
    "        left = 0\n",
    "        right = sum_ - beans[0]\n",
    "\n",
    "        res = left + right - (len(beans) - 1) * beans[0]\n",
    "        left += beans[0]\n",
    "        right -= beans[1]\n",
    "        for i in range(1, len(beans)):\n",
    "            if beans[i] != beans[i - 1]:\n",
    "                res = min(res, left + right - (len(beans) - i - 1) * beans[i])\n",
    "            \n",
    "            if i == len(beans) - 1:\n",
    "                break\n",
    "                \n",
    "            left += beans[i]\n",
    "            right -= beans[i + 1]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        beans.sort()\n",
    "        total = sum(beans)\n",
    "        res = total\n",
    "        for i in range(len(beans)):\n",
    "            tmp = total - beans[i]*(len(beans)-i)\n",
    "            if res > tmp:\n",
    "                res = tmp\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        r=math.inf\n",
    "        beans.sort()\n",
    "        n=len(beans)\n",
    "        totle=sum(beans)\n",
    "        for i in range(n):\n",
    "            c=0         \n",
    "            c+=totle-beans[i]*(n-i)\n",
    "            if c<r:\n",
    "                r=c  \n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        beans.sort()\n",
    "        s = sum(beans)\n",
    "        ans = s\n",
    "        t = 0\n",
    "        n = len(beans)\n",
    "        for i, x in enumerate(beans):\n",
    "            if i != 0 and beans[i] == beans[i - 1]:\n",
    "                continue\n",
    "            ans = min(ans, s - (n - i) * x)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        n = len(beans)\n",
    "        beans.sort()\n",
    "        total = sum(beans)   # 豆子总数\n",
    "        res = total   # 最少需要移除的豆子数\n",
    "        for i in range(n):\n",
    "            res = min(res, total - beans[i] * (n - i))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        beans.sort()\n",
    "        print(beans)\n",
    "        result = []\n",
    "        for i in range(len(beans)):\n",
    "            result.append((len(beans)-i)*beans[i])\n",
    "        return sum(beans) - max(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\r\n",
    "        # 袋子数量\r\n",
    "        n = len(beans)\r\n",
    "        # 排序\r\n",
    "        beans = sorted(beans)\r\n",
    "        # 总数\r\n",
    "        s = sum(beans)\r\n",
    "        # 第i个袋子豆子不变，最终可保留的豆子总数量\r\n",
    "        t = [(n-i) * v for i, v in enumerate(beans)]\r\n",
    "        \r\n",
    "        return s - max(t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import bisect\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        # 对beans进行排序\n",
    "        beans.sort()\n",
    "\n",
    "        l = len(beans)\n",
    "        # 生成beans的前缀和，保存到变量prefixSum中\n",
    "        prefixSum = [0] * l\n",
    "        for i in range(len(beans)):\n",
    "            prefixSum[i] = prefixSum[i - 1] + beans[i]\n",
    "\n",
    "        # 初始化ans为prefixSum的最后一个元素减去第一个元素乘以beans的长度\n",
    "        ans = 10000000001\n",
    "        # 遍历beans，计算ans的最小值\n",
    "        for i in range(0, len(beans)):\n",
    "            ans = min(ans, prefixSum[-1] - (l - i) * beans[i])\n",
    "        # 返回ans\n",
    "        return ans\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    s = Solution()\n",
    "    # 测试示例1\n",
    "    assert 4 == s.minimumRemoval([4, 1, 6, 5])\n",
    "    # 测试示例2\n",
    "    assert 7 == s.minimumRemoval([2, 10, 3, 2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        beans.sort()\n",
    "        n = len(beans)\n",
    "        s = [0] * (n + 1)\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            s[i + 1] = s[i] + beans[i]\n",
    "            ret += beans[i]\n",
    "        for i in range(n):\n",
    "            ret = min(s[n] - s[i] - (n - i) * beans[i] + s[i], ret)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: [int]) -> int:\n",
    "\n",
    "        beans.sort()\n",
    "        n = len(beans)  # nums为待计算前缀和的数组\n",
    "        pre = list(accumulate(beans))  # pre[i] 为[0..i]这i+1个数字的和\n",
    "        pre.insert(0, 0)  # sum[i,j]= pre[j+1] - pre[i]\n",
    "\n",
    "        tot=sum(beans)\n",
    "        for p in range(n):                                  #p表示 0..p-1 之前的都去掉， 从p位开始保留\n",
    "            if p>0 and beans[p]==beans[p-1]: continue\n",
    "            precut=pre[p]-pre[0]         #第p位置之前的全部都去掉\n",
    "            succcut=pre[n]-pre[p]\n",
    "            succcut=succcut- (n-p)*beans[p]\n",
    "            tot=min(tot,precut+succcut)\n",
    "\n",
    "        return tot\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: [int]) -> int:\n",
    "\n",
    "        beans.sort()\n",
    "        n = len(beans)  # nums为待计算前缀和的数组\n",
    "        pre = list(accumulate(beans))  # pre[i] 为[0..i]这i+1个数字的和\n",
    "        pre.insert(0, 0)  # sum[i,j]= pre[j+1] - pre[i]\n",
    "\n",
    "        tot=sum(beans)\n",
    "        for p in range(n):                                  #p表示 0..p-1 之前的都去掉， 从p位开始保留\n",
    "#            if p>0 and beans[p]==beans[p-1]: continue\n",
    "            precut=pre[p]-pre[0]         #第p位置之前的全部都去掉\n",
    "            succcut=pre[n]-pre[p]\n",
    "            succcut=succcut- (n-p)*beans[p]\n",
    "            tot=min(tot,precut+succcut)\n",
    "\n",
    "        return tot\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        beans.sort()\n",
    "        n = len(beans)\n",
    "        pre = list(accumulate(beans))\n",
    "        ans = pre[-1]\n",
    "        for i in range(n):\n",
    "            cur = pre[i] + pre[-1] - pre[i] - (n-i)*beans[i]\n",
    "            if cur < ans:\n",
    "                ans = cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\r\n",
    "        beans.sort()\r\n",
    "        pre_sum = [0]\r\n",
    "        for i in range(len(beans)):\r\n",
    "            pre_sum.append(pre_sum[-1] + beans[i])\r\n",
    "        ans = float('inf')\r\n",
    "        n = len(beans)\r\n",
    "        for i in range(n):\r\n",
    "            before = pre_sum[i]\r\n",
    "            after = pre_sum[-1] - pre_sum[i+1] - beans[i] * (n - i - 1)\r\n",
    "            ans = min(ans, before + after)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        beans.sort()\n",
    "        n = len(beans)\n",
    "        pre = list(accumulate(beans, initial=0))\n",
    "        ans = inf\n",
    "        for i in range(n):\n",
    "            s1 = pre[i]\n",
    "            s2 = pre[-1] - pre[i] - (n-i) * beans[i]\n",
    "            ans = min(ans, s1 + s2)\n",
    "        return ans\n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        n = len(beans)\n",
    "        beans.sort()\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        a = [beans[0]]\n",
    "        for i in range(1, n):\n",
    "            a.append(beans[i] + a[-1])\n",
    "        res = float('inf')\n",
    "        for i in range(n):\n",
    "            minus = 0\n",
    "            if i > 0:\n",
    "                minus = a[i-1]\n",
    "            add = 0\n",
    "            if i + 1 < n:\n",
    "                add = (a[-1] - a[i]) - beans[i] * (n-1-i)\n",
    "            res = min(res, add + minus)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\r\n",
    "        beans.sort()\r\n",
    "        pre_sum = [0]\r\n",
    "        for i in range(len(beans)):\r\n",
    "            pre_sum.append(pre_sum[-1] + beans[i])\r\n",
    "        ans = float('inf')\r\n",
    "        for i in range(len(beans)):\r\n",
    "            before = pre_sum[i]\r\n",
    "            after = pre_sum[-1] - pre_sum[i+1] - beans[i] * (len(beans) - i - 1)\r\n",
    "            ans = min(ans, before + after)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import bisect\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        beans.sort()\n",
    "        prefixSum = []\n",
    "        sum = 0\n",
    "        for bean in beans:\n",
    "            sum += bean\n",
    "            prefixSum.append(sum)\n",
    "\n",
    "        l = len(beans)\n",
    "        ans = prefixSum[-1] - beans[0] * l\n",
    "        for i in range(1, len(beans)):\n",
    "            if beans[i] == beans[i - 1]:\n",
    "                continue\n",
    "\n",
    "            ans = min(\n",
    "                ans,\n",
    "                prefixSum[-1] - beans[i] * (l - i),\n",
    "            )\n",
    "        return ans\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    s = Solution()\n",
    "    assert 4 == s.minimumRemoval([4, 1, 6, 5])\n",
    "    assert 7 == s.minimumRemoval([2, 10, 3, 2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        beans.sort()\n",
    "        n = len(beans)\n",
    "        presum = [0]\n",
    "        for i in range(n):\n",
    "            presum.append(presum[-1] + beans[i])\n",
    "        ans = inf\n",
    "        for i in range(n):\n",
    "            temp = presum[-1] - (n - i) * beans[i]\n",
    "            ans = min(ans, temp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        beans.sort()\n",
    "        n = len(beans)\n",
    "        presum = list(accumulate(beans, initial=0))\n",
    "        ans = inf\n",
    "        for i in range(n-1, -1, -1):\n",
    "            suf = presum[n] - presum[i]\n",
    "            ans = min(ans, suf - beans[i] * (n-i) + presum[i])\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        beans.sort(key = lambda x:-x)\n",
    "        perfix = [0]*(len(beans)+1)\n",
    "        \n",
    "        for i in range(1,len(perfix)):\n",
    "            perfix[i] = perfix[i-1] + beans[i-1]\n",
    "    \n",
    "        b = 0\n",
    "        res = inf \n",
    "        while b < len(beans): \n",
    "            # 枚举选豆子的代价\n",
    "            max_sum = perfix[b] - b*beans[b]\n",
    "            while b+1 < len(beans) and beans[b] == beans[b+1]:\n",
    "                b += 1\n",
    "            min_sum = perfix[-1] - perfix[b+1] \n",
    "            res = min(res,max_sum + min_sum)\n",
    "            b += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumRemoval(self, beans: List[int]) -> int:\n",
    "        n = len(beans)\n",
    "        cnt = Counter(beans)\n",
    "        keys = list(cnt.keys())\n",
    "        keys.sort()\n",
    "        #print(keys)\n",
    "        ans = inf\n",
    "        n = len(beans)\n",
    "        sum_ = sum(beans)\n",
    "\n",
    "        pre_sum = 0\n",
    "        pre_num_sum = 0\n",
    "        for i, key in enumerate(keys):\n",
    "            num = cnt[key]\n",
    "            after_num = n - pre_num_sum - num\n",
    "            tmp = sum_  - key * (after_num) - key * (num)\n",
    "\n",
    "            pre_num_sum += num\n",
    "            pre_sum += key * num\n",
    "\n",
    "            ans = min(ans, tmp)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
